package com.justnow.offer;

/**
 * @author justnow
 * Created on 2020-09-17
 * Description
 *
 * 这条直径可能穿过根节点，也可能不穿过根节点
 */
public class Solution55 {
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }

    public int depth(TreeNode node) {
        if (node == null) return 0; //访问到空节点了，返回0
        int L = depth(node.left);   // 左儿子为根的子树的深度
        int R = depth(node.right);  // 右儿子为根的子树的深度
        ans = Math.max(ans, L+R+1); // 计算d_node 即 L+R+1 并更新ans
        return Math.max(L, R) + 1;  // 返回该节点为根的子树的深度
    }
}

class TreeNode {
    int val;
    TreeNode left, right;
}